package com.fallsvc.dayproblem.demo202511;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @auther falls_vc
 * description:
 * @date 2025/11/11  14:51
 */
public class Demo20251111 {
//    给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
    public List<List<Integer>> ret;
    public List<Integer> path;
    public boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        used = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums);
        return ret;
    }

    private void dfs(int[] nums) {
        if(path.size() == nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(used[i]) continue;
            if(i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            path.add(nums[i]);
            used[i] = true;
            dfs(nums);
            // 回溯
            path.remove(path.size()-1);
            used[i] = false;
        }
    }


//    https://leetcode.cn/problems/container-with-most-water/submissions/606692962/
//    给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
    //    找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
    //    返回容器可以储存的最大水量。
    public int maxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;

        int ret = 0;

        while(l < r) {
            if (height[l] <= height[r]) {
                ret = Math.max(ret,(r-l) * height[l]);
                l++;
            } else {

                ret = Math.max(ret,(r-l) * height[r]);
                r--;
            }
        }

        return ret;

    }
}
